/*
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

��Դ�����ۣ�LeetCode��
���ӣ�https://leetcode-cn.com/problems/longest-palindromic-substring
����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
*/

#include <string>

using namespace std;

class Solution {
public:
	bool checkIsPalidromicString(string s)
	{
		int nSLength = s.length();

		if (s.empty())
		{
			return false;
		}

		if (nSLength == 1)
		{
			return true;
		}

		int nStart = 0;
		int nEnd = nSLength - 1;

		while (nStart < nEnd)
		{
			if (s[nStart] != s[nEnd])
			{
				return false;
			}

			nStart++;
			nEnd--;
		}

		return true;
	}

	string longestPalindrome1(string s) {
		string strLongest = "";

		int nSLength = s.length();

		int nStart = 0;
		int nEnd = nSLength - 1;

		while (nStart <= nEnd)
		{
			int i = nStart;
			int j = nEnd;

			int nCurLength = strLongest.length();

			while (j - i + 1 > nCurLength)
			{
				string strSubString = s.substr(i, j - i + 1);
				bool bPalindromic = this->checkIsPalidromicString(strSubString);

				if (bPalindromic)
				{
					strLongest = strSubString;
					nCurLength = strLongest.length();
				}
				j--;
			}

			nStart++;
		}

		return strLongest;
	}

	// string longestPalindrome2(string s) {
	// 	string strLongest = "";

	// 	int nSLength = s.length();

	// 	for (int i = 0; i < nSLength; i++)
	// 	{
	// 		int nCurSubLength = strLongest.length();
	// 		int nLongerLength = nCurSubLength + 1;

	// 		if (nLongerLength % 2 == 0)
	// 		{
	// 			int nStart = i - nLongerLength / 2;
	// 			int nEnd = i + nLongerLength / 2;
	// 			int m = i;
	// 			int n = i + 1;
	// 			while (m >= nStart && n < nEnd)
	// 			{
	// 				if (s[m] == s[n])
	// 				{
	// 				}
	// 			}
	// 		}

	// 		while (nStart >= 0 && nEnd < nSLength)
	// 		{
	// 			if (s[nStart] == s[nEnd])
	// 			{
	// 				nHalfLength++;
	// 			}
	// 			else
	// 			{
	// 				nStart++;
	// 				nEnd--;
	// 				strLongest = s.substr(nStart, nEnd - nStart + 1);
	// 			}
	// 		}
	// 	}

	// 	return strLongest;
	// }
};
